package code.oldCode.feishuSpecializedTraining.dynamic;

/**
 * @author 26029
 * @date 2025/3/26
 * @description
 */
public class MyDP7 {
    // 121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        // 1 <= prices.length <= 105
        int len = prices.length;
        // 分状态，buy[i]表示前i天买，sell[i]表示前i天卖，获得的最大利润
        // 状态分先后，先买后卖，一次（意味着sell[i]要用到buy[i]）
        int[] buy = new int[len];
        int[] sell = new int[len];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i] = Math.max(-prices[i], buy[i - 1]);
            sell[i] = Math.max(sell[i - 1], buy[i] + prices[i]);
        }
        return sell[len - 1];
    }

    // 122. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        // 1 <= prices.length <= 3 * 104
        int len = prices.length;
        // 分状态，have[i]表示第i天持有，no[i]表示第i天不持有
        // 状态不分先后（意味着have[i] no[i]只和i-1有关）
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0];
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 1] - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return Math.max(have[len - 1], no[len - 1]);
    }

    // 123. 买卖股票的最佳时机 III
    public int maxProfit3(int[] prices) {
        // 1 <= prices.length <= 105
        int len = prices.length;
        // 分状态，buy1[i]表示前i天买第一次，sell1[i]表示前i天卖第一次，获取的最大利润
        // buy2[i] sell2[i]同理
        // 状态分先后！
        int[] buy1 = new int[len];
        int[] sell1 = new int[len];
        int[] buy2 = new int[len];
        int[] sell2 = new int[len];
        buy1[0] = buy2[0] = -prices[0];
        sell1[0] = sell2[0] = 0;
        for (int i = 1; i < len; i++) {
            buy1[i] = Math.max(buy1[i - 1], -prices[i]);
            sell1[i] = Math.max(sell1[i - 1], buy1[i] + prices[i]);
            buy2[i] = Math.max(buy2[i - 1], sell1[i] - prices[i]);
            sell2[i] = Math.max(sell2[i - 1], buy2[i] + prices[i]);
        }
        return sell2[len - 1];
    }
}
